{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Bridge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestBridge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短的桥"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>n x n</code> 的二元矩阵 <code>grid</code> ，其中 <code>1</code> 表示陆地，<code>0</code> 表示水域。</p>\n",
    "\n",
    "<p><strong>岛</strong> 是由四面相连的 <code>1</code> 形成的一个最大组，即不会与非组内的任何其他 <code>1</code> 相连。<code>grid</code> 中 <strong>恰好存在两座岛</strong> 。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>你可以将任意数量的 <code>0</code> 变为 <code>1</code> ，以使两座岛连接起来，变成 <strong>一座岛</strong> 。</p>\n",
    "\n",
    "<p>返回必须翻转的 <code>0</code> 的最小数目。</p>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1],[1,0]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1,0],[0,0,0],[0,0,1]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li><code>grid</code> 中恰有两个岛</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-bridge](https://leetcode.cn/problems/shortest-bridge/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-bridge](https://leetcode.cn/problems/shortest-bridge/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,0]]', '[[0,1,0],[0,0,0],[0,0,1]]', '[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        first_x, first_y = -1, -1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    first_x, first_y = i, j\n",
    "                    break\n",
    "        \n",
    "        # def dfs(x, y):\n",
    "        #     grid[x][j] = 2\n",
    "        #     bfs_queue.append((x, y))\n",
    "        #     for cur_x, cur_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "        #         if 0 <= cur_x < n and 0 <= cur_y < n and grid[cur_x][cur_y] == 1:\n",
    "        #             dfs(cur_x, cur_y)\n",
    "        \n",
    "        # bfs_queue = []\n",
    "        # dfs(first_x, first_y)\n",
    "\n",
    "        # distance = 0\n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "            bfs_queue.append((x, y))\n",
    "            for cur_x, cur_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if 0 <= cur_x < n and 0 <= cur_y < n and grid[cur_x][cur_y] == 1:\n",
    "                    dfs(cur_x, cur_y)\n",
    "        \n",
    "        # Add all land cells of island A to bfs_queue.\n",
    "        bfs_queue = []\n",
    "        dfs(first_x, first_y)\n",
    "        \n",
    "        distance = 0\n",
    "        while bfs_queue:\n",
    "            new_bfs = []\n",
    "            for x, y in bfs_queue:\n",
    "                for cur_x, cur_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if 0 <= cur_x < n and 0 <= cur_y < n:\n",
    "                        if grid[cur_x][cur_y] == 1:\n",
    "                            return distance\n",
    "                        elif grid[cur_x][cur_y] == 0:\n",
    "                            new_bfs.append((cur_x, cur_y))\n",
    "                            grid[cur_x][cur_y] = -1\n",
    "\n",
    "            bfs_queue = new_bfs\n",
    "            distance += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        h = len(A)\n",
    "        w = len(A[0])\n",
    "        \n",
    "        # find the first A[i][j] == 1\n",
    "        def find_first_one(h, w):\n",
    "            for i in range(h):\n",
    "                for j in range(w):\n",
    "                    if A[i][j] == 1:\n",
    "                        return i, j\n",
    "                    \n",
    "        ci, cj = find_first_one(h, w)\n",
    "        \n",
    "        \n",
    "        # get the elements in the first island\n",
    "        seed = [[ci, cj]] \n",
    "        bfs = [] # store the elements in A and A[i][j] == 0, and it has a neihbor == 1\n",
    "              \n",
    "        while seed:\n",
    "            i, j = seed.pop()\n",
    "            A[i][j] = -1\n",
    "            for ci, cj in [[i - 1, j], [i, j + 1], [i + 1, j], [i, j - 1]]:\n",
    "                if not (ci >=0 and ci < h and cj >= 0 and cj < w) or A[ci][cj] == -1: # this i, j in A and hasn't been visited\n",
    "                    continue\n",
    "                if A[ci][cj] == 1:\n",
    "                    seed.append([ci, cj])\n",
    "                elif A[ci][cj] == 0:\n",
    "                    A[ci][cj] = 2\n",
    "                    bfs.append([ci, cj])\n",
    "        \n",
    "        # broad first search rest elements, layer by layer\n",
    "        \n",
    "        d = 2\n",
    "        while bfs: \n",
    "            nex_bfs = [] # store the elements that are zeros and also are the neighbors of current bfs layer\n",
    "            for i, j in bfs:\n",
    "                A[i][j] = -1\n",
    "                for ci, cj in [[i - 1, j], [i, j + 1], [i + 1, j], [i, j - 1]]:\n",
    "                    if ci < 0 or cj < 0 or ci >= h or cj >= w or A[ci][cj] == d or A[ci][cj] == -1:\n",
    "                        continue\n",
    "                    if A[ci][cj] == 1:\n",
    "                        return d - 1\n",
    "                    A[ci][cj] = d\n",
    "                    nex_bfs.append([ci, cj])\n",
    "            d += 1\n",
    "            bfs = nex_bfs\n",
    "        \n",
    "        \n",
    "        # Time complexity O(h * w), Space complexity O(h * w)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        if len(A) == 0:\n",
    "            return 0\n",
    "        posi = -1\n",
    "        posj = -1\n",
    "        flag = False\n",
    "        for i in range(len(A)):\n",
    "            if flag:\n",
    "                break\n",
    "            for j in range(len(A[0])):\n",
    "                if A[i][j] == 1:\n",
    "                    posi = i\n",
    "                    posj = j\n",
    "                    flag = not flag\n",
    "                    break\n",
    "        if posi == -1:\n",
    "            return 0\n",
    "        stack = [[posi,posj]]\n",
    "        A[posi][posj] = 2\n",
    "        list1 = []\n",
    "        while (len(stack) > 0):\n",
    "            cur = stack.pop(-1)\n",
    "            pi,pj = cur[0],cur[1]\n",
    "            if pi - 1 >= 0 and A[pi - 1][pj] == 1:\n",
    "                A[pi - 1][pj] = 2\n",
    "                stack.append([pi - 1, pj])\n",
    "            if pi + 1 <= len(A) - 1 and A[pi + 1][pj] == 1:\n",
    "                A[pi + 1][pj] = 2\n",
    "                stack.append([pi + 1, pj])\n",
    "            if pj - 1 >= 0 and A[pi][pj - 1] == 1:\n",
    "                A[pi][pj-1] = 2\n",
    "                stack.append([pi, pj - 1])\n",
    "            if pj + 1 <= len(A[0]) - 1 and A[pi][pj + 1] == 1:\n",
    "                A[pi][pj+1] = 2\n",
    "                stack.append([pi, pj + 1])\n",
    "            list1.append([cur[0],cur[1]])\n",
    "        list2 = []\n",
    "        for i in range(len(A)):\n",
    "            for j in range(len(A[0])):\n",
    "                if A[i][j] == 1:\n",
    "                    list2.append([i,j])\n",
    "        minpos = 500\n",
    "        for i in list1:\n",
    "            for j in list2:\n",
    "                minpos = min(minpos,abs(j[0]-i[0])+abs(j[1]-i[1])-1)\n",
    "        return minpos\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    " \n",
    "\n",
    "               \"\"\"\n",
    "        m=len(A)\n",
    "        visit=set()\n",
    "        queue=collections.deque()\n",
    "        newq=collections.deque()\n",
    "        \n",
    "        found=False\n",
    "        for i in range(m):\n",
    "            if found:\n",
    "                break\n",
    "                \n",
    "            for j in range(m): \n",
    "                \n",
    "                if A[i][j]==1:\n",
    "                    visit.add((i,j))\n",
    "                    queue.append((i,j))\n",
    "                    found=True\n",
    "                    break\n",
    "        while queue:\n",
    "            i,j=queue.popleft()\n",
    "            for x,y in [(i,j+1),(1+i,j),(i-1,j),(i,j-1)]:\n",
    "                if 0<=x<m and 0<=y<m and (x,y) not in visit:\n",
    "                    if A[x][y]==1:\n",
    "                        visit.add((x,y))\n",
    "                        queue.append((x,y))\n",
    "                    elif A[x][y]==0:\n",
    "                        \n",
    "                        newq.append((x,y,3))\n",
    "\n",
    "        \n",
    "        while newq:\n",
    "            i,j,step=newq.popleft()            \n",
    "            \n",
    "            for x,y in [(i,j+1),(1+i,j),(i-1,j),(i,j-1)]:\n",
    "\n",
    "                if 0<=x<m and 0<=y<m and (x,y) not in visit:\n",
    "                    if A[x][y]==0:\n",
    "                        visit.add((x,y))\n",
    "                        newq.append((x,y,step+1))\n",
    "                    elif A[x][y]==1:\n",
    "                        return step-2  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        q = []\n",
    "        for y in range(len(A)):\n",
    "            for x in range(len(A[0])):\n",
    "                if A[y][x] == 1:\n",
    "                    self.dfs(A, x, y, q)\n",
    "                    break\n",
    "            else:\n",
    "                continue\n",
    "            break\n",
    "\n",
    "        steps, dirs = 0, (0, 1, 0, -1, 0)\n",
    "        while len(q):\n",
    "            size = len(q)\n",
    "            while size:\n",
    "                x, y = q.pop(0)\n",
    "                for i in range(4):\n",
    "                    tx, ty = x + dirs[i], y + dirs[i + 1]\n",
    "                    if tx < 0 or ty < 0 or tx >= len(A[0]) or ty >= len(A) or A[ty][tx] == 2:\n",
    "                        continue\n",
    "                    if A[ty][tx] == 1:\n",
    "                        return steps\n",
    "                    A[ty][tx] = 2\n",
    "                    q.append((tx, ty))\n",
    "                size -= 1\n",
    "            steps += 1\n",
    "        return -1\n",
    "        \n",
    "        \n",
    "    def dfs(self, arr, x, y, q):\n",
    "        if x < 0 or y < 0 or x >= len(arr[0]) or y >= len(arr) or not arr[y][x] == 1:\n",
    "            return None\n",
    "        arr[y][x] = 2\n",
    "        q.append((x, y))\n",
    "        self.dfs(arr, x - 1, y, q)\n",
    "        self.dfs(arr, x + 1, y, q)\n",
    "        self.dfs(arr, x, y - 1, q)\n",
    "        self.dfs(arr, x, y + 1, q)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        M, N = len(A), len(A[0])\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        visited = [[0] * N for _ in range(M)]\n",
    "        hasfind = False\n",
    "        que = collections.deque()\n",
    "        for i in range(M):\n",
    "            if hasfind: break\n",
    "            for j in range(N):\n",
    "                if A[i][j] == 1:\n",
    "                    self.dfs(A, i, j, visited, que)\n",
    "                    hasfind = True\n",
    "                    break\n",
    "        step = 0\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            for _ in range(size):\n",
    "                i, j = que.popleft()\n",
    "                for d in dirs:\n",
    "                    x, y = i + d[0], j + d[1]\n",
    "                    if 0 <= x < M and 0 <= y < N:\n",
    "                        visited[x][y] = 1\n",
    "                        if A[x][y] == 1:\n",
    "                            return step\n",
    "                        elif A[x][y] == 0:\n",
    "                            A[x][y] = 2\n",
    "                            que.append((x, y))\n",
    "                        else:\n",
    "                            continue\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "    def dfs(self, A, i, j, visited, que):\n",
    "        if visited[i][j]: return\n",
    "        visited[i][j] = 1\n",
    "        M, N = len(A), len(A[0])\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        if A[i][j] == 1:\n",
    "            que.append((i, j))\n",
    "            A[i][j] = 2\n",
    "            for d in dirs:\n",
    "                x, y = i + d[0], j + d[1]\n",
    "                if 0 <= x < M and 0 <= y < N:\n",
    "                    self.dfs(A, x, y, visited, que)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        found = False\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        pointQueue = []\n",
    "        count = 0\n",
    "\n",
    "        for i in range(0, len(A)):\n",
    "            for j in range(0, len(A[0])):\n",
    "                if not found and A[i][j] == 1:\n",
    "                    self.dfs(A, i, j)\n",
    "                    found = True\n",
    "                if found and A[i][j] == 1:\n",
    "                    pointQueue.append((i, j))\n",
    "\n",
    "        while pointQueue:\n",
    "            size = len(pointQueue)\n",
    "            for i in range(0, size):\n",
    "                x, y = pointQueue.pop(0)\n",
    "                for dirx, diry in dirs:\n",
    "                    tx, ty = x + dirx, y + diry\n",
    "                    if tx < 0 or tx >= len(A) or ty < 0 or ty >= len(A[0]):\n",
    "                        continue\n",
    "                    if A[tx][ty] == 0:\n",
    "                        A[tx][ty] = 1\n",
    "                        pointQueue.append((tx, ty))\n",
    "                    if A[tx][ty] == 2:\n",
    "                        return count\n",
    "            count += 1\n",
    "\n",
    "    def dfs(self, A, i, j):\n",
    "        if i < 0 or i >= len(A) or j < 0 or j >= len(A[0]) or A[i][j] == 2 or A[i][j] == 0:\n",
    "            return\n",
    "\n",
    "        A[i][j] = 2\n",
    "        self.dfs(A, i+1, j)\n",
    "        self.dfs(A, i-1, j)\n",
    "        self.dfs(A, i, j+1)\n",
    "        self.dfs(A, i, j-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestBridge(self, A):\n",
    "        R, C = len(A), len(A[0])\n",
    "\n",
    "        def neighbors(r, c):\n",
    "            for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):\n",
    "                if 0 <= nr < R and 0 <= nc < C:\n",
    "                    yield nr, nc\n",
    "\n",
    "        def get_components():\n",
    "            done = set()\n",
    "            components = []\n",
    "            for r, row in enumerate(A):\n",
    "                for c, val in enumerate(row):\n",
    "                    if val and (r, c) not in done:\n",
    "                        # Start dfs\n",
    "                        stack = [(r, c)]\n",
    "                        seen = {(r, c)}\n",
    "                        while stack:\n",
    "                            node = stack.pop()\n",
    "                            for nei in neighbors(*node):\n",
    "                                if A[nei[0]][nei[1]] and nei not in seen:\n",
    "                                    stack.append(nei)\n",
    "                                    seen.add(nei)\n",
    "                        done |= seen\n",
    "                        components.append(seen)\n",
    "            return components\n",
    "\n",
    "        source, target = get_components()\n",
    "        # print source, target\n",
    "        queue = collections.deque([(node, 0) for node in source])\n",
    "        done = set(source)\n",
    "        while queue:\n",
    "            node, d = queue.popleft()\n",
    "            if node in target: return d-1\n",
    "            for nei in neighbors(*node):\n",
    "                if nei not in done:\n",
    "                    queue.append((nei, d+1))\n",
    "                    done.add(nei)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestBridge(self, A):\n",
    "        R, C = len(A), len(A[0])\n",
    "\n",
    "        def neighbors(r, c):\n",
    "            for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):\n",
    "                if 0 <= nr < R and 0 <= nc < C:\n",
    "                    yield nr, nc\n",
    "\n",
    "        def get_components():\n",
    "            done = set()\n",
    "            components = []\n",
    "            for r, row in enumerate(A):\n",
    "                for c, val in enumerate(row):\n",
    "                    if val and (r, c) not in done:\n",
    "                        # Start dfs\n",
    "                        stack = [(r, c)]\n",
    "                        seen = {(r, c)}\n",
    "                        while stack:\n",
    "                            node = stack.pop()\n",
    "                            for nei in neighbors(*node):\n",
    "                                if A[nei[0]][nei[1]] and nei not in seen:\n",
    "                                    stack.append(nei)\n",
    "                                    seen.add(nei)\n",
    "                        done |= seen\n",
    "                        components.append(seen)\n",
    "            return components\n",
    "\n",
    "        source, target = get_components()\n",
    "        # print source, target\n",
    "        queue = collections.deque([(node, 0) for node in source])\n",
    "        done = set(source)\n",
    "        while queue:\n",
    "            node, d = queue.popleft()\n",
    "            if node in target: return d-1\n",
    "            for nei in neighbors(*node):\n",
    "                if nei not in done:\n",
    "                    queue.append((nei, d+1))\n",
    "                    done.add(nei)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        w = len(A)\n",
    "        nd = 2\n",
    "        ndset = []\n",
    "        cur_min = w * w\n",
    "\n",
    "        def dfs(x, y):\n",
    "            nonlocal A, ndset, cur_min\n",
    "            A[x][y] = nd\n",
    "            ct = 0\n",
    "            for _x, _y in [(max(x - 1, 0), y), (min(x + 1, w - 1), y),\n",
    "                           (x, max(y - 1, 0)), (x, min(y + 1, w - 1))]:\n",
    "                if A[_x][_y] == 1:\n",
    "                    dfs(_x, _y)\n",
    "                    ct += 1\n",
    "                elif A[_x][_y] == nd:\n",
    "                    ct += 1\n",
    "            if ct < 4:\n",
    "                if nd == 2:\n",
    "                    ndset.append((x, y))  # edge\n",
    "                else:\n",
    "                    for x2, y2 in ndset:\n",
    "                        dst = abs(x2 - x) + abs(y2 - y) - 1\n",
    "                        cur_min = min(dst, cur_min)\n",
    "\n",
    "        for x in range(w):\n",
    "            for y in range(w):\n",
    "                if A[x][y] == 1:\n",
    "                    dfs(x, y)\n",
    "                    nd += 1\n",
    "        if nd != 4:\n",
    "            return 0\n",
    "        else:\n",
    "            return cur_min\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x, y, r, c = 0, 0, len(A), len(A[0])\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if A[i][j] == 1:\n",
    "                    x, y = i, j\n",
    "                    break\n",
    "            else:\n",
    "                continue\n",
    "            break\n",
    "\n",
    "        d = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = [[0]*c for _ in range(r)]\n",
    "        islandA, result = list(), 0\n",
    "        def _floodfill(i, j):\n",
    "            if 0 <= i < r and 0 <= j < c and not visited[i][j] and A[i][j] == 1:\n",
    "                visited[i][j] = 1\n",
    "                islandA.append((i, j))\n",
    "                for k in range(4):\n",
    "                    _floodfill(i + d[k][0], j + d[k][1])\n",
    "\n",
    "        _floodfill(x, y)\n",
    "        while islandA:\n",
    "            stack = list()\n",
    "            for i, j in islandA:\n",
    "                if i - 1 >= 0 and not visited[i-1][j]:\n",
    "                    if A[i-1][j] == 1:\n",
    "                        return result\n",
    "                    else:\n",
    "                        stack.append((i-1, j))\n",
    "                        visited[i-1][j] = 1\n",
    "                if i + 1 < r and not visited[i+1][j]:\n",
    "                    if A[i+1][j] == 1:\n",
    "                        return result\n",
    "                    else:\n",
    "                        stack.append((i+1, j))\n",
    "                        visited[i+1][j] = 1\n",
    "                if j - 1 >= 0 and not visited[i][j-1]:\n",
    "                    if A[i][j-1] == 1:\n",
    "                        return result\n",
    "                    else:\n",
    "                        stack.append((i, j-1))\n",
    "                        visited[i][j-1] = 1\n",
    "                if j + 1 < c and not visited[i][j+1]:\n",
    "                    if A[i][j+1] == 1:\n",
    "                        return result\n",
    "                    else:\n",
    "                        stack.append((i, j+1))\n",
    "                        visited[i][j+1] = 1\n",
    "            islandA = stack\n",
    "            result += 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a = set()\n",
    "        def dfs(x,y):\n",
    "            nonlocal a\n",
    "            # print(x,y)\n",
    "            if x <0 or x >= len(A) or y < 0 or y >= len(A[0]) or A[x][y] != 1 or (x,y) in a:\n",
    "                return\n",
    "            \n",
    "            a.add((x,y))\n",
    "            dfs(x-1,y)\n",
    "            dfs(x+1,y)\n",
    "            dfs(x,y-1)\n",
    "            dfs(x,y+1)\n",
    "        for i,v in enumerate(A):\n",
    "            mark = False\n",
    "            for j,vt in enumerate(v):\n",
    "                if vt == 1:\n",
    "                    dfs(i,j)\n",
    "                    mark = True\n",
    "                    break\n",
    "            if mark:\n",
    "                break\n",
    "        ans = -1\n",
    "        l = set()\n",
    "        alls = set(a)\n",
    "        # print(a)\n",
    "        for x,y in a:\n",
    "            if x-1 >= 0 and A[x-1][y] == 0 or x+1 < len(A) and A[x+1][y] == 0 or y-1 >= 0 and A[x][y-1] == 0 or y+1 < len(A[0]) and A[x][y+1] == 0:\n",
    "                l.add((x,y))\n",
    "                # alls.add((x,y))\n",
    "                \n",
    "        # print(l)\n",
    "        while True:\n",
    "            ans += 1\n",
    "            temp = set()\n",
    "            for x,y in l:\n",
    "                \n",
    "                if x-1 >= 0  and (x-1,y) not in alls and A[x-1][y] == 1:\n",
    "                    return ans\n",
    "                if x+1 < len(A) and (x+1,y) not in alls and A[x+1][y] ==1 :\n",
    "                    return ans\n",
    "                if y-1 >= 0 and (x,y-1) not in alls and A[x][y-1] == 1:\n",
    "                    return ans\n",
    "                if y+1 < len(A[0]) and (x,y+1) not in alls and A[x][y+1] == 1:\n",
    "                    return ans\n",
    "                if x-1 >= 0 and A[x-1][y] == 0 :\n",
    "                    temp.add((x-1,y))\n",
    "                    alls.add((x-1,y))\n",
    "                if x+1 < len(A) and A[x+1][y] == 0:\n",
    "                    temp.add((x+1,y))\n",
    "                    alls.add((x+1,y))\n",
    "                if y-1 >= 0 and A[x][y-1] == 0:\n",
    "                    temp.add((x,y-1))\n",
    "                    alls.add((x,y-1))\n",
    "                if y+1 < len(A[0]) and A[x][y+1] == 0:\n",
    "                    temp.add((x,y+1))\n",
    "                    alls.add((x,y+1))\n",
    "                    \n",
    "            # print(l)        \n",
    "            l = temp\n",
    "        \n",
    "        \n",
    "        \n",
    "        # while True:\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A: List[List[int]]) -> int:\n",
    "        a, spread, border, flag = len(A), [], [], False\n",
    "        for i in range(a):\n",
    "            for j in range(a):\n",
    "                if A[i][j]:  # 找到任一岛屿的起始点\n",
    "                    A[i][j] = -1  # 置为已访问\n",
    "                    spread.append((i, j))\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                break\n",
    "        step = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        while spread:  # bfs找该岛屿的所有部分\n",
    "            i, j = spread.pop(0)\n",
    "            neighbor = 0\n",
    "            if i == 0 or i == a-1:\n",
    "                neighbor += 1\n",
    "            if j == 0 or j == a-1:\n",
    "                neighbor += 1\n",
    "            for di, dj in step:\n",
    "                _i, _j = i+di, j+dj\n",
    "                if -1 < _i < a and -1 < _j < a:\n",
    "                    if A[_i][_j] == 1:\n",
    "                        neighbor += 1\n",
    "                        A[_i][_j] = -1  # 置为已访问\n",
    "                        spread.append((_i, _j))  # 加入队列\n",
    "                    elif A[_i][_j] == -1:\n",
    "                        neighbor += 1\n",
    "            if neighbor < 4:  # 邻居小于4则该坐标为岛屿边界点\n",
    "                border.append((i, j, 0))\n",
    "        while True:  # 对边界点进行BFS扩散\n",
    "            i, j, n = border.pop(0)\n",
    "            for di, dj in step:\n",
    "                _i, _j = i+di, j+dj\n",
    "                if -1 < _i < a and -1 < _j < a:\n",
    "                    if not A[_i][_j]:  # 仅当该位置为0才加入队列\n",
    "                        A[_i][_j] = -1  # 置为已访问\n",
    "                        border.append((_i, _j, n+1))\n",
    "                    elif A[_i][_j] == 1:  # 为1则找到，为-1则跳过\n",
    "                        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A: List[List[int]]) -> int:\n",
    "        a, spread, border, flag = len(A), [], [], False\n",
    "        for i in range(a):\n",
    "            for j in range(a):\n",
    "                if A[i][j]:  # 找到任一岛屿的起始点\n",
    "                    A[i][j] = -1  # 置为已访问\n",
    "                    spread.append((i, j))\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                break\n",
    "        step = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        while spread:  # bfs找该岛屿的所有部分\n",
    "            i, j = spread.pop(0)\n",
    "            neighbor = 0\n",
    "            if i == 0 or i == a-1:\n",
    "                neighbor += 1\n",
    "            if j == 0 or j == a-1:\n",
    "                neighbor += 1\n",
    "            for di, dj in step:\n",
    "                _i, _j = i+di, j+dj\n",
    "                if -1 < _i < a and -1 < _j < a:\n",
    "                    if A[_i][_j] == 1:\n",
    "                        neighbor += 1\n",
    "                        A[_i][_j] = -1  # 置为已访问\n",
    "                        spread.append((_i, _j))  # 加入队列\n",
    "                    elif A[_i][_j] == -1:\n",
    "                        neighbor += 1\n",
    "            if neighbor < 4:  # 邻居小于4则该坐标为岛屿边界点\n",
    "                border.append((i, j, 0))\n",
    "        while True:  # 对边界点进行BFS扩散\n",
    "            i, j, n = border.pop(0)\n",
    "            for di, dj in step:\n",
    "                _i, _j = i+di, j+dj\n",
    "                if -1 < _i < a and -1 < _j < a:\n",
    "                    if not A[_i][_j]:  # 仅当该位置为0才加入队列\n",
    "                        A[_i][_j] = -1  # 置为已访问\n",
    "                        border.append((_i, _j, n+1))\n",
    "                    elif A[_i][_j] == 1:  # 为1则找到，为-1则跳过\n",
    "                        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef shortestBridge(self,A):\n",
    "\t\tisland,B=[],[i[:] for i in A] #先复制一个A 算是后面有用8 空间换时间\n",
    "\t\tfor r in range(len(A)): #首先要找到其中一个岛的随便一块地的位置\n",
    "\t\t\tfor c in range(len(A[0])):\n",
    "\t\t\t\tt=A[r][c]\n",
    "\t\t\t\tif t==1:\n",
    "\t\t\t\t\tisland.append((r,c))\n",
    "\t\t\t\t\tB[r][c]=-1\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\tif len(island):\n",
    "\t\t\t\tbreak\n",
    "\t\tborder=[] #一个岛所有边界上的地的坐标位置\n",
    "\t\twhile island:\n",
    "\t\t\tnew_island=[]\n",
    "\t\t\tfor i,j in island:\n",
    "\t\t\t\tcnt=0 #对每一块地都要观测它是不是岛屿边缘地带\n",
    "\t\t\t\tfor r,c in ((i,j-1),(i,j+1),(i-1,j),(i+1,j)):\n",
    "\t\t\t\t\ttry:\n",
    "\t\t\t\t\t\tassert r>=0 and c>=0 #坐标需要合法\n",
    "\t\t\t\t\t\tif A[r][c]==1: #坐标不能出界\n",
    "\t\t\t\t\t\t\tcnt+=1\n",
    "\t\t\t\t\t\t\tif B[r][c]==1:\n",
    "\t\t\t\t\t\t\t\tnew_island.append((r,c))\n",
    "\t\t\t\t\t\t\t\tB[r][c]=-1\n",
    "\t\t\t\t\texcept:\n",
    "\t\t\t\t\t\tcontinue\n",
    "\t\t\t\tif cnt!=4:\n",
    "\t\t\t\t\tborder.append((i,j))\n",
    "\t\t\tisland=new_island\n",
    "\t\tturn=0\n",
    "\t\twhile True:\n",
    "\t\t\tnew_border=[]\n",
    "\t\t\tfor i,j in border:\n",
    "\t\t\t\tfor r,c in ((i,j-1),(i,j+1),(i-1,j),(i+1,j)):\n",
    "\t\t\t\t\ttry:\n",
    "\t\t\t\t\t\tassert r>=0 and c>=0\n",
    "\t\t\t\t\t\tt=B[r][c]\n",
    "\t\t\t\t\t\tif t==0:\n",
    "\t\t\t\t\t\t\tnew_border.append((r,c))\n",
    "\t\t\t\t\t\t\tB[r][c]=-1\n",
    "\t\t\t\t\t\telif t==1:\n",
    "\t\t\t\t\t\t\treturn turn\n",
    "\t\t\t\t\texcept:\n",
    "\t\t\t\t\t\tcontinue\n",
    "\t\t\tborder=new_border\n",
    "\t\t\tturn+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A: List[List[int]]) -> int:\n",
    "        n=len(A)\n",
    "        A.append([2]*n)\n",
    "        for x in A: x.append(2)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if A[i][j]==1:\n",
    "                    a,st,A[i][j],s=[(i,j)],[(i,j)],2,0\n",
    "                    while st:\n",
    "                        i,j=st.pop()\n",
    "                        for i,j in (i,j+1),(i+1,j),(i,j-1),(i-1,j):\n",
    "                            if A[i][j]==1:\n",
    "                                a.append((i,j))\n",
    "                                st.append((i,j))\n",
    "                                A[i][j]=2\n",
    "                    while 1:\n",
    "                        b=[]\n",
    "                        for i,j in a:\n",
    "                            for i,j in (i,j+1),(i+1,j),(i,j-1),(i-1,j):\n",
    "                                if A[i][j]==1: return s\n",
    "                                elif not A[i][j]:\n",
    "                                    b.append((i,j))\n",
    "                                    A[i][j]=2\n",
    "                        a,s=b,s+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def Color(self,A,color,r,c):\n",
    "        '''将邻接点染色并且把边界着色为-color,返回边界点的坐标列表,是否和其他边界碰撞'''\n",
    "        cur = [(r,c)]\n",
    "        clide = False\n",
    "        boundary = []\n",
    "        while len(cur)!=0:\n",
    "            ncur = []\n",
    "            for c in cur:\n",
    "                if A[c[0]][c[1]]==1:\n",
    "                    A[c[0]][c[1]]=color\n",
    "                    tmp = []\n",
    "                    if c[0]-1>=0:\n",
    "                        tmp.append((c[0]-1,c[1]))\n",
    "                    if c[0]+1<len(A):\n",
    "                        tmp.append((c[0]+1,c[1]))\n",
    "                    if c[1]-1>=0:\n",
    "                        tmp.append((c[0],c[1]-1))\n",
    "                    if c[1]+1<len(A[0]):\n",
    "                        tmp.append((c[0],c[1]+1))\n",
    "                    for t in tmp:\n",
    "                        if A[t[0]][t[1]]==1:\n",
    "                            ncur.append(t)\n",
    "                        elif A[t[0]][t[1]]==0:\n",
    "                            boundary.append(t)\n",
    "                            A[t[0]][t[1]] = -color\n",
    "                        elif A[t[0]][t[1]]==color:\n",
    "                            pass\n",
    "                        elif A[t[0]][t[1]]==-color:\n",
    "                            pass\n",
    "                        else: #碰到了另一种boundary\n",
    "                            return [],True\n",
    "            cur = ncur\n",
    "        return boundary,False\n",
    "\n",
    "    def extend(self,bound,A):\n",
    "        bcolor = A[bound[0][0]][bound[0][1]]\n",
    "        cur = bound\n",
    "        nbound = []\n",
    "        for c in cur:\n",
    "            tmp = []\n",
    "            if c[0]-1>=0:\n",
    "                tmp.append((c[0]-1,c[1]))\n",
    "            if c[0]+1<len(A):\n",
    "                tmp.append((c[0]+1,c[1]))\n",
    "            if c[1]-1>=0:\n",
    "                tmp.append((c[0],c[1]-1))\n",
    "            if c[1]+1<len(A[0]):\n",
    "                tmp.append((c[0],c[1]+1))\n",
    "            for t in tmp:\n",
    "                if A[t[0]][t[1]]>0: #碰到了自己的大陆\n",
    "                    pass\n",
    "                elif A[t[0]][t[1]]==0: #新边界\n",
    "                    nbound.append(t)\n",
    "                    A[t[0]][t[1]] = bcolor\n",
    "                elif A[t[0]][t[1]]==bcolor: #碰到了自己的边界\n",
    "                    pass\n",
    "                else: #碰到了别人的边界\n",
    "                    return [],True\n",
    "        return nbound,False\n",
    "\n",
    "\n",
    "\n",
    "    def shortestBridge(self, A: List[List[int]]) -> int:\n",
    "        row = len(A)\n",
    "        col = len(A[0])\n",
    "        color = 2\n",
    "        blen = 0\n",
    "        bound2 = []\n",
    "        bound3 = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if A[i][j]==1:\n",
    "                    bound,clide = self.Color(A,color,i,j)\n",
    "                    if color==2:\n",
    "                        bound2 = bound\n",
    "                    elif color==3:\n",
    "                        bound3 = bound\n",
    "                    if clide:\n",
    "                        return blen\n",
    "                    blen += 1\n",
    "                    color += 1\n",
    "                if color==4:\n",
    "                    break\n",
    "        #print(A,blen,bound2,bound3)\n",
    "        while True:\n",
    "            bound2,clide = self.extend(bound2,A)\n",
    "            #print(A,blen,clide)\n",
    "            if clide:\n",
    "                return blen\n",
    "            blen += 1\n",
    "            bound3,clide = self.extend(bound3,A)\n",
    "            if clide:\n",
    "                return blen\n",
    "            blen += 1\n",
    "\n",
    "        return blen\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A) -> int:\n",
    "        # 1、更新map，区分两个岛\n",
    "        edges = None\n",
    "        for i in range(len(A)):\n",
    "            flag = False\n",
    "            for j in range(len(A)):\n",
    "                if A[i][j]==1:\n",
    "                    edges = self.update(A,i,j)\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                break\n",
    "\n",
    "        # print(A)\n",
    "        # print(edges)\n",
    "        cnt = 0\n",
    "        while edges:\n",
    "            # print(A)\n",
    "            n = len(edges)\n",
    "            for _ in range(n):\n",
    "                pos_i,pos_j = edges.pop(0)\n",
    "                temp_edges,flag = self.expand(A,pos_i,pos_j)\n",
    "                if flag:\n",
    "                    return cnt\n",
    "                edges +=temp_edges\n",
    "            cnt+=1\n",
    "\n",
    "\n",
    "    def expand(self,A,pos_i,pos_j):\n",
    "        new_edge = []\n",
    "        flag = False\n",
    "        if pos_i - 1 >= 0 and A[pos_i - 1][pos_j] != 2:\n",
    "            if pos_i - 1 >= 0 and A[pos_i - 1][pos_j]==1:\n",
    "                flag =True\n",
    "\n",
    "            A[pos_i-1][pos_j]=2\n",
    "            new_edge.append([pos_i-1,pos_j])\n",
    "\n",
    "        if pos_j - 1 >= 0 and A[pos_i][pos_j - 1] != 2:\n",
    "            if pos_j - 1 >= 0 and A[pos_i ][pos_j-1]==1:\n",
    "                flag =True\n",
    "            A[pos_i][pos_j-1]=2\n",
    "            new_edge.append([pos_i,pos_j-1])\n",
    "\n",
    "        if pos_i + 1 < len(A) and A[pos_i + 1][pos_j] != 2:\n",
    "            if pos_i+ 1 <len(A) and A[pos_i + 1][pos_j]==1:\n",
    "                flag =True\n",
    "            A[pos_i+1][pos_j]=2\n",
    "            new_edge.append([pos_i+1,pos_j])\n",
    "\n",
    "        if pos_j + 1 < len(A) and A[pos_i][pos_j + 1] != 2:\n",
    "            if pos_j + 1 < len(A) and A[pos_i][pos_j + 1]==1:\n",
    "                flag = True\n",
    "            A[pos_i][pos_j+1]=2\n",
    "            new_edge.append([pos_i,pos_j+1])\n",
    "\n",
    "        return new_edge,flag\n",
    "\n",
    "    def update(self,A,i,j):\n",
    "        A[i][j]=2\n",
    "        adjs = [[i,j]]\n",
    "        edges = []\n",
    "        while adjs:\n",
    "            pos_i,pos_j = adjs.pop(0)\n",
    "            if self.isEdge(A,pos_i,pos_j):\n",
    "                edges.append([pos_i,pos_j])\n",
    "\n",
    "            if pos_i-1>=0 and A[pos_i-1][pos_j]==1:\n",
    "                A[pos_i-1][pos_j]=2\n",
    "                adjs.append([pos_i-1,pos_j])\n",
    "\n",
    "            if pos_j-1>=0 and A[pos_i][pos_j-1]==1:\n",
    "                A[pos_i][pos_j-1]=2\n",
    "                adjs.append([pos_i,pos_j-1])\n",
    "\n",
    "            if pos_i+1<len(A) and A[pos_i+1][pos_j]==1:\n",
    "                A[pos_i+1][pos_j]=2\n",
    "                adjs.append([pos_i+1,pos_j])\n",
    "\n",
    "            if pos_j+1<len(A) and A[pos_i][pos_j+1]==1:\n",
    "                A[pos_i][pos_j+1]=2\n",
    "                adjs.append([pos_i,pos_j+1])\n",
    "\n",
    "        return edges\n",
    "\n",
    "    def isEdge(self,A,pos_i,pos_j):\n",
    "\n",
    "        if pos_i - 1 >= 0 and A[pos_i - 1][pos_j] == 0:\n",
    "            return True\n",
    "\n",
    "        if pos_j - 1 >= 0 and A[pos_i][pos_j - 1] == 0:\n",
    "            return True\n",
    "\n",
    "        if pos_i + 1 < len(A) and A[pos_i + 1][pos_j] == 0:\n",
    "            return True\n",
    "\n",
    "        if pos_j + 1 < len(A) and A[pos_i][pos_j + 1] == 0:\n",
    "            return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A: List[List[int]]) -> int:\n",
    "        queue, path = [], []\n",
    "        row, col = len(A), len(A[0])\n",
    "\n",
    "        def is_judge(ls):\n",
    "            return True if (0 <= ls[0] < row) and (0 <= ls[1] < col) else False\n",
    "\n",
    "        def get_one(a_num):\n",
    "            for h in range(0, row):\n",
    "                if a_num in A[h]:\n",
    "                    return [h, A[h].index(a_num)]\n",
    "\n",
    "        queue.append(get_one(1))\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            i, j = cur[0], cur[1]\n",
    "            path.append([i, j])\n",
    "            A[i][j] = 2\n",
    "            for a in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:\n",
    "                if is_judge(a) and A[a[0]][a[1]] == 1:\n",
    "                    A[a[0]][a[1]] = 2\n",
    "                    queue.append(a)\n",
    "        print(A)\n",
    "        queue = path\n",
    "        count = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                i, j = cur[0], cur[1]\n",
    "                for a in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:\n",
    "                    if is_judge(a) and A[a[0]][a[1]] != 2:\n",
    "                        if A[a[0]][a[1]] == 1:\n",
    "                            return count\n",
    "                        A[a[0]][a[1]] = 2\n",
    "                        queue.append(a)\n",
    "            count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIsland(self, A: List[List[int]], i: int, j: int) -> List[List[List[int]]]:\n",
    "        r = len(A)\n",
    "        c = len(A[0])\n",
    "        island = [[i, j]]\n",
    "        q = [[i, j]]                      \n",
    "        while q:\n",
    "            x = q[-1][0]\n",
    "            y = q[-1][1]\n",
    "            A[x][y] = 2\n",
    "            q.pop()\n",
    "            if x - 1 >= 0 and A[x-1][y] == 1:\n",
    "                q.append([x-1, y])\n",
    "                island.append([x-1, y])\n",
    "            if x + 1 < r and A[x+1][y] == 1:\n",
    "                q.append([x+1, y])\n",
    "                island.append([x+1, y])\n",
    "            if y - 1 >= 0 and A[x][y-1] == 1:\n",
    "                q.append([x, y-1])\n",
    "                island.append([x, y-1])\n",
    "            if y + 1 < c and A[x][y+1] == 1:\n",
    "                q.append([x, y+1])\n",
    "                island.append([x, y+1])\n",
    "        return island\n",
    "\n",
    "    def shortestBridge(self, A: List[List[int]]) -> int:\n",
    "        r = len(A)\n",
    "        c = len(A[0])\n",
    "        flag1 = False\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if A[i][j] == 1:\n",
    "                    flag1 = True\n",
    "                    break\n",
    "            if flag1:\n",
    "                break      \n",
    "        first_island = self.findIsland(A, i, j)\n",
    "        #print(i, j, first_island, A)\n",
    "        cnt = 0\n",
    "        while first_island:            \n",
    "            first_island_len = len(first_island)\n",
    "            for i in range(first_island_len):               \n",
    "                q = first_island[0]\n",
    "                #print(q)\n",
    "                x = q[0]\n",
    "                y = q[1]\n",
    "                first_island.pop(0)\n",
    "                if x - 1 >= 0 and A[x-1][y] == 1:\n",
    "                    return cnt\n",
    "                if x + 1 < r and A[x+1][y] == 1:\n",
    "                    return cnt\n",
    "                if y - 1 >= 0 and A[x][y-1] == 1:\n",
    "                    return cnt\n",
    "                if y + 1 < c and A[x][y+1] == 1:\n",
    "                    return cnt\n",
    "                if x - 1 >= 0 and A[x-1][y] == 0:                    \n",
    "                    first_island.append([x-1, y])\n",
    "                    A[x-1][y] = 2\n",
    "                if x + 1 < r and A[x+1][y] == 0:\n",
    "                    first_island.append([x+1, y])\n",
    "                    A[x+1][y] = 2\n",
    "                if y - 1 >= 0 and A[x][y-1] == 0:\n",
    "                    first_island.append([x, y-1])\n",
    "                    A[x][y-1] = 2\n",
    "                if y + 1 < c and A[x][y+1] == 0:\n",
    "                    first_island.append([x, y+1])\n",
    "                    A[x][y+1] = 2\n",
    "            if len(first_island) > 0:\n",
    "                cnt += 1\n",
    "                #print(first_island, cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestBridge(self, A):\n",
    "        R, C = len(A), len(A[0])\n",
    "\n",
    "        def neighbors(r, c):\n",
    "            for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):\n",
    "                if 0 <= nr < R and 0 <= nc < C:\n",
    "                    yield nr, nc\n",
    "\n",
    "        def get_components():\n",
    "            done = set()\n",
    "            components = []\n",
    "            for r, row in enumerate(A):\n",
    "                for c, val in enumerate(row):\n",
    "                    if val and (r, c) not in done:\n",
    "                        # Start dfs\n",
    "                        stack = [(r, c)]\n",
    "                        seen = {(r, c)}\n",
    "                        while stack:\n",
    "                            node = stack.pop()\n",
    "                            for nei in neighbors(*node):\n",
    "                                if A[nei[0]][nei[1]] and nei not in seen:\n",
    "                                    stack.append(nei)\n",
    "                                    seen.add(nei)\n",
    "                        done |= seen\n",
    "                        components.append(seen)\n",
    "            return components\n",
    "\n",
    "        source, target = get_components()\n",
    "\n",
    "        queue = collections.deque([(node, 0) for node in source])\n",
    "        done = set(source)\n",
    "        while queue:\n",
    "            node, d = queue.popleft()\n",
    "            if node in target: return d-1\n",
    "            for nei in neighbors(*node):\n",
    "                if nei not in done:\n",
    "                    queue.append((nei, d+1))\n",
    "                    done.add(nei)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "from typing import List\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\r\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "\r\n",
    "        def find_first():\r\n",
    "            for i in range(m):\r\n",
    "                for j in range(n):\r\n",
    "                    if grid[i][j] == 1:\r\n",
    "                        return (i, j)\r\n",
    "\r\n",
    "        first = find_first()\r\n",
    "        heap = [(0, first)]\r\n",
    "        grid[first[0]][first[1]] = 2\r\n",
    "        while heap:\r\n",
    "            level, pos = heapq.heappop(heap)\r\n",
    "            curr_i, curr_j = pos\r\n",
    "            for d_i, d_j in directions:\r\n",
    "                new_i, new_j = curr_i + d_i, curr_j + d_j\r\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] <= 1:\r\n",
    "                    if level > 0 and grid[new_i][new_j] == 1:\r\n",
    "                        return level\r\n",
    "                    heapq.heappush(heap, (0 if level == 0 and grid[new_i][new_j] == 1 else (level + 1), (new_i, new_j)))\r\n",
    "                    grid[new_i][new_j] = 2\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        # 找第一个岛屿\n",
    "        n = len(grid)\n",
    "        dirs = [(-1,0), (1,0), (0,-1), (0,1)]\n",
    "        # 找第一个岛屿\n",
    "        ## 第一个岛屿的起始点\n",
    "        que = deque([])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    que.append((i,j))\n",
    "                    grid[i][j]=2\n",
    "                    break\n",
    "            if len(que)>0: break\n",
    "        ## 以que为起点、BFS找到第一个岛屿的所有点、并标记为2\n",
    "        island1=deque([que[0]])\n",
    "        while que:\n",
    "            x,y = que.popleft()\n",
    "            for dx,dy in dirs:\n",
    "                x1, y1 = x+dx, y+dy\n",
    "                if 0<=x1<n and 0<=y1<n and grid[x1][y1]==1:\n",
    "                    que.append((x1, y1))\n",
    "                    grid[x1][y1]=2\n",
    "                    island1.append((x1,y1))\n",
    "        # 以island1为起点 找到第二个岛屿中的点\n",
    "        step=0\n",
    "        len_=len(island1)\n",
    "        while island1:\n",
    "            step+=1\n",
    "            for _ in range(len_):\n",
    "                x, y = island1.popleft()\n",
    "                for dx, dy in dirs:\n",
    "                    x1, y1 = x+dx,y+dy\n",
    "                    if not(0<=x1<n and 0<=y1<n):\n",
    "                        continue \n",
    "                    if grid[x1][y1]==1:\n",
    "                        return step-1\n",
    "                    if grid[x1][y1]==0:\n",
    "                        island1.append((x1,y1))\n",
    "                        grid[x1][y1]=2\n",
    "            len_ = len(island1)\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dirs=[(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        for i,g in enumerate(grid):\n",
    "            for j,v in enumerate(g):\n",
    "                if v==0:\n",
    "                    continue\n",
    "                q=deque([(i,j)])\n",
    "                grid[i][j]=-1\n",
    "                island=[]\n",
    "                while q:\n",
    "                    x,y=q.popleft()\n",
    "                    island.append((x,y))\n",
    "                    for dx,dy in dirs:\n",
    "                        nx=dx+x\n",
    "                        ny=dy+y\n",
    "                        if 0<=nx<m and 0<=ny<n and grid[nx][ny]==1:\n",
    "                            q.append((nx,ny))\n",
    "                            grid[nx][ny]=-1\n",
    "                step=0\n",
    "                q=island\n",
    "                while True:\n",
    "                    tmp=q\n",
    "                    q=[]\n",
    "                    for x,y in tmp:\n",
    "                        for dx,dy in dirs:\n",
    "                            nx=dx+x\n",
    "                            ny=dy+y\n",
    "                            if 0<=nx<m and 0<=ny<n:\n",
    "                                if grid[nx][ny]==1:\n",
    "                                    return step\n",
    "                                if grid[nx][ny]==0:\n",
    "                                    grid[nx][ny]=-1\n",
    "                                    q.append((nx,ny))\n",
    "                    step+=1\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q = collections.deque([(i, j)])\n",
    "                    island = collections.deque([(i, j)])\n",
    "                    grid[i][j] = 2\n",
    "                    while q:\n",
    "                        a, b = q.popleft()\n",
    "                        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                            nx, ny = a + dx, b + dy \n",
    "                            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                                grid[nx][ny] = 2 \n",
    "                                q.append((nx, ny))\n",
    "                                island.append((nx, ny))\n",
    "                    step = 0\n",
    "                    while island:\n",
    "                        for _ in range(len(island)):\n",
    "                            x, y = island.popleft()\n",
    "                            for nx, ny in [(x + 1, y), (x - 1, y), (x, y -1), (x, y + 1)]:\n",
    "                                if 0 <= nx < m and 0 <= ny < n:\n",
    "                                    if grid[nx][ny] == 1:\n",
    "                                        return step \n",
    "                                    if grid[nx][ny] == 0:\n",
    "                                        grid[nx][ny] = 2 \n",
    "                                        island.append((nx, ny))\n",
    "                        step += 1\n",
    "\n",
    "        \n",
    "        \n",
    "    \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=1:\n",
    "                    continue\n",
    "                island=[]\n",
    "                grid[i][j]=-1\n",
    "                q=[]\n",
    "                q.append((i,j))\n",
    "                while q:\n",
    "                    x,y=q.pop(0)\n",
    "                    island.append((x,y))\n",
    "                    for nx,ny in (x+1,y), (x-1,y), (x,y+1), (x,y-1):\n",
    "                        if 0<=nx<m and 0<=ny<n:\n",
    "                            if grid[nx][ny]==1:\n",
    "                                grid[nx][ny]=-1\n",
    "                                q.append((nx,ny))\n",
    "                print(island)\n",
    "                \n",
    "                step=0\n",
    "                q=island\n",
    "                while True:\n",
    "                    tmp=q\n",
    "                    q=[]\n",
    "                    for x,y in tmp:\n",
    "                        for nx,ny in (x+1,y), (x-1,y), (x,y+1), (x,y-1):\n",
    "                            if 0<=nx<n and 0<=ny<n:\n",
    "                                if grid[nx][ny]==1:\n",
    "                                    return step\n",
    "                                if grid[nx][ny]==0:\n",
    "                                    grid[nx][ny]=-1\n",
    "                                    q.append((nx,ny))\n",
    "                    step+=1\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        dx = [0,0,1,-1]\n",
    "        dy = [1,-1,0,0]\n",
    "        queue = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append([i,j])\n",
    "                    grid[i][j] = 0\n",
    "                    break\n",
    "            if queue:\n",
    "                break\n",
    "        new_queue = [[i,j]]\n",
    "        while queue:\n",
    "            j = queue.pop()\n",
    "            for i in range(4):\n",
    "                node_x = j[0] + dx[i]\n",
    "                node_y = j[1] + dy[i]\n",
    "                if not (0<=node_x<=len(grid)-1 and 0<=node_y<=len(grid)-1) or grid[node_x][node_y] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    queue.append([node_x,node_y])\n",
    "                    new_queue.append([node_x,node_y])\n",
    "                    grid[node_x][node_y] = 0\n",
    "        res = 0\n",
    "        \n",
    "        for x in range(len(grid)):\n",
    "            q = []\n",
    "            res += 1\n",
    "            for n in new_queue:\n",
    "                for i in range(4):\n",
    "                    node_x = n[0] + dx[i]\n",
    "                    node_y = n[1] + dy[i]\n",
    "                    if not (0<=node_x<=len(grid)-1 and 0<=node_y<=len(grid)-1) or grid[node_x][node_y] == 2:\n",
    "                        continue\n",
    "                    elif grid[node_x][node_y] == 0:\n",
    "                        q.append([node_x, node_y])\n",
    "                        grid[node_x][node_y] = 2\n",
    "                    else:\n",
    "                        return res-1\n",
    "            new_queue = q\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fill(self, grid):\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 2\n",
    "                    queue = deque([(i, j)])\n",
    "                    while queue:\n",
    "                        a, b = queue.popleft()\n",
    "                        for x, y in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):\n",
    "                            if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:\n",
    "                                grid[x][y] = 2\n",
    "                                queue.append((x, y))\n",
    "                    return grid\n",
    "\n",
    "\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        grid = self.fill(grid)\n",
    "        n = len(grid)\n",
    "        ans = n * n      \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 2:\n",
    "                    grid[i][j] = 10\n",
    "                    queue = deque([(i, j)])\n",
    "                    while queue:\n",
    "                        for rr in range(len(queue)):\n",
    "                            a, b = queue.popleft()\n",
    "                            for x, y in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):\n",
    "                                if 0 <= x < n and 0 <= y < n:\n",
    "                                    if grid[x][y] == 2:\n",
    "                                        grid[x][y] = 10\n",
    "                                        queue.append((x, y))\n",
    "                                    elif grid[x][y] == 0:\n",
    "                                        grid[x][y] = grid[a][b] + 1\n",
    "                                        queue.append((x, y))\n",
    "                                    elif grid[x][y] == 1:\n",
    "                                        ans = min(ans, grid[a][b] - 10)\n",
    "                                    elif grid[x][y] >= 10:\n",
    "                                        if grid[a][b] + 1 < grid[x][y]:\n",
    "                                            grid[x][y] = grid[a][b] + 1\n",
    "                                            queue.append((x, y))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        judge = []\n",
    "        border = []\n",
    "        for i in range(n):\n",
    "            judge.append([False] * n)\n",
    "        for i in range(n):\n",
    "            flag1 = False\n",
    "            for j in range(n):\n",
    "                flag = False\n",
    "                if grid[i][j] == 1:\n",
    "                    flag = True\n",
    "                    judge[i][j] = True\n",
    "                    queue = [[i, j]]\n",
    "                    while len(queue) != 0:\n",
    "                        temp = queue.pop(0)\n",
    "                        y, x = temp[0], temp[1]\n",
    "                        if x + 1 < n:\n",
    "                            if grid[y][x + 1] == 1 and not judge[y][x + 1]:\n",
    "                                judge[y][x + 1] = True\n",
    "                                queue.append([y, x + 1])\n",
    "                            if grid[y][x + 1] == 0 and not judge[y][x + 1]:\n",
    "                                judge[y][x + 1] = True\n",
    "                                border.append([y, x + 1, 1])\n",
    "                        if x - 1 >= 0:\n",
    "                            if grid[y][x - 1] == 1 and not judge[y][x - 1]:\n",
    "                                judge[y][x - 1] = True\n",
    "                                queue.append([y, x - 1])\n",
    "                            if grid[y][x - 1] == 0 and not judge[y][x - 1]:\n",
    "                                judge[y][x - 1] = True\n",
    "                                border.append([y, x - 1, 1])                            \n",
    "                        if y + 1 < n:\n",
    "                            if grid[y + 1][x] == 1 and not judge[y + 1][x]:\n",
    "                                judge[y + 1][x] = True\n",
    "                                queue.append([y + 1, x])\n",
    "                            if grid[y + 1][x] == 0 and not judge[y + 1][x]:\n",
    "                                judge[y + 1][x] = True\n",
    "                                border.append([y + 1, x, 1])\n",
    "                        if y - 1 >= 0:\n",
    "                            if grid[y - 1][x] == 1 and not judge[y - 1][x]:\n",
    "                                judge[y - 1][x] = True\n",
    "                                queue.append([y - 1, x, 1])\n",
    "                            if grid[y - 1][x] == 0 and not judge[y - 1][x]:\n",
    "                                judge[y - 1][x] = True\n",
    "                                border.append([y - 1, x, 1])\n",
    "                if flag:\n",
    "                    flag1 = True\n",
    "                    break\n",
    "            if flag1:\n",
    "                break\n",
    "        while len(border) != 0:\n",
    "            temp = border.pop(0)\n",
    "            y, x, count = temp[0], temp[1], temp[2]\n",
    "            if x + 1 < n:\n",
    "                if grid[y][x + 1] == 0 and not judge[y][x + 1]:\n",
    "                    judge[y][x + 1] = True\n",
    "                    border.append([y, x + 1, count + 1])\n",
    "                elif grid[y][x + 1] == 1 and not judge[y][x + 1]:\n",
    "                    return count\n",
    "            if x - 1 >= 0:\n",
    "                if grid[y][x - 1] == 0 and not judge[y][x - 1]:\n",
    "                    judge[y][x - 1] = True\n",
    "                    border.append([y, x - 1, count + 1])\n",
    "                elif grid[y][x - 1] == 1 and not judge[y][x - 1]:\n",
    "                    return count\n",
    "            if y + 1 < n:\n",
    "                if grid[y + 1][x] == 0 and not judge[y + 1][x]:\n",
    "                    judge[y + 1][x] = True\n",
    "                    border.append([y + 1, x, count + 1])\n",
    "                elif grid[y + 1][x] == 1 and not judge[y + 1][x]:\n",
    "                    return count            \n",
    "            if y - 1 >= 0:\n",
    "                if grid[y - 1][x] == 0 and not judge[y - 1][x]:\n",
    "                    judge[y - 1][x] = True\n",
    "                    border.append([y - 1, x, count + 1])\n",
    "                elif grid[y - 1][x] == 1 and not judge[y - 1][x]:\n",
    "                    return count        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n=len(grid)\n",
    "\n",
    "        cnt=2\n",
    "        iland=[]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    tmp=[]\n",
    "                    stack=collections.deque()\n",
    "                    grid[i][j]=0\n",
    "                    stack.append([i,j])\n",
    "                    while stack:\n",
    "                        x,y=stack.pop()\n",
    "                        tmp.append([x,y])\n",
    "                        for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                            if 0<=x1<n and 0<=y1<n and grid[x1][y1]==1:\n",
    "                                grid[x1][y1]=0\n",
    "                                stack.append([x1,y1])\n",
    "                    iland.append(tmp)\n",
    "        mx=n*n \n",
    "        #print(iland)\n",
    "        for x1,y1 in iland[0]:\n",
    "            for x2,y2 in iland[1]:\n",
    "                d=abs(x1-x2)+abs(y1-y2)-1\n",
    "                if mx>d:\n",
    "                    mx=d\n",
    "        \n",
    "        return mx   \n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "\n",
    "        n = len(A)\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if A[i][j] == 1:\n",
    "                    q.append([i, j])\n",
    "                    A[i][j] = 2\n",
    "                    break\n",
    "            if len(q) > 0:\n",
    "                break\n",
    "\n",
    "        l = 0\n",
    "        r = 1\n",
    "        while l < r:\n",
    "            nowx, nowy = q[l]\n",
    "            l += 1\n",
    "            for index in range(4):\n",
    "                x = nowx + dx[index]\n",
    "                y = nowy + dy[index]\n",
    "                if x >= 0 and x < n and y >= 0 and y < n and A[x][y] == 1:\n",
    "                    A[x][y] = 2\n",
    "                    q.append([x, y])\n",
    "                    r += 1\n",
    "\n",
    "        l = 0\n",
    "        r = len(q)\n",
    "        step = 0\n",
    "        while l < r:\n",
    "            step += 1\n",
    "            for nowx, nowy in q[l : r]:\n",
    "                for index in range(4):\n",
    "                    x = nowx + dx[index]\n",
    "                    y = nowy + dy[index]\n",
    "                    if x >= 0 and x < n and y >= 0 and y < n:\n",
    "                        if A[x][y] == 0:\n",
    "                            A[x][y] = 2\n",
    "                            q.append([x, y])\n",
    "                        elif A[x][y] == 1:\n",
    "                            return step - 1\n",
    "            \n",
    "            l, r = r, len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(i,j):\n",
    "            seen = {(i,j)}\n",
    "            level = {(i,j)}\n",
    "            while level:\n",
    "                nextlevel = set()\n",
    "                for r, c in level:\n",
    "                    for nr, nc in [(r-1,c), (r,c-1), (r,c+1), (r+1,c)]:\n",
    "                        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] and (nr,nc) not in seen:\n",
    "                            seen.add((nr,nc))\n",
    "                            nextlevel.add((nr,nc))\n",
    "                level = nextlevel\n",
    "            return seen\n",
    "        \n",
    "        n = len(grid)\n",
    "        A, B = set(), set()\n",
    "        for i in range(n):\n",
    "            if B:\n",
    "                break\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    continue\n",
    "                if not A:\n",
    "                    A = func(i,j)\n",
    "                elif (i,j) not in A:    # 关键条件！！！\n",
    "                    B = func(i,j)\n",
    "                    break\n",
    "        front, end = A, B\n",
    "        visit = front | end\n",
    "        bridge = 0\n",
    "        while front:\n",
    "            newfront = set()\n",
    "            for r, c in front:\n",
    "                for nr, nc in [(r-1,c), (r,c-1), (r,c+1), (r+1,c)]:\n",
    "                    if 0 <= nr < n and 0 <= nc < n:\n",
    "                        if (nr,nc) in end:\n",
    "                            return bridge\n",
    "                        if (nr,nc) not in visit:\n",
    "                            visit.add((nr,nc))\n",
    "                            newfront.add((nr,nc))\n",
    "            bridge += 1\n",
    "            front = newfront\n",
    "            if len(front) > len(end):\n",
    "                front, end = end, front\n",
    "        return bridge\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(i,j):\n",
    "            seen = {(i,j)}\n",
    "            level = {(i,j)}\n",
    "            while level:\n",
    "                nextlevel = set()\n",
    "                for r, c in level:\n",
    "                    for nr, nc in [(r-1,c), (r,c-1), (r,c+1), (r+1,c)]:\n",
    "                        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] and (nr,nc) not in seen:\n",
    "                            seen.add((nr,nc))\n",
    "                            nextlevel.add((nr,nc))\n",
    "                level = nextlevel\n",
    "            return seen\n",
    "        \n",
    "        n = len(grid)\n",
    "        A, B = set(), set()\n",
    "        for i in range(n):\n",
    "            if B:\n",
    "                break\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    continue\n",
    "                if not A:\n",
    "                    A = func(i,j)\n",
    "                elif (i,j) not in A:\n",
    "                    B = func(i,j)\n",
    "                    break\n",
    "        front, end = A, B\n",
    "        visit = front | end\n",
    "        bridge = 0\n",
    "        while front:\n",
    "            newfront = set()\n",
    "            for r, c in front:\n",
    "                for nr, nc in [(r-1,c), (r,c-1), (r,c+1), (r+1,c)]:\n",
    "                    if 0 <= nr < n and 0 <= nc < n:\n",
    "                        if (nr,nc) in end:\n",
    "                            return bridge\n",
    "                        if (nr,nc) not in visit:\n",
    "                            visit.add((nr,nc))\n",
    "                            newfront.add((nr,nc))\n",
    "            bridge += 1\n",
    "            front = newfront\n",
    "            if len(front) > len(end):\n",
    "                front, end = end, front\n",
    "        return bridge\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self,N):\n",
    "        self.parents = [i for i in range(N)]\n",
    "\n",
    "    def find(self,x):\n",
    "        st = x \n",
    "        while self.parents[x] != x:\n",
    "            x = self.parents[x]\n",
    "        self.parents[st] = x\n",
    "        return x\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        self.parents[self.find(x)] = self.find(y)\n",
    "        \n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        # 并查集+BFS\n",
    "        dsu = DSU(len(grid)*len(grid[0]))\n",
    "        dirs = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    for m,n in dirs:\n",
    "                        x = i + m\n",
    "                        y = j + n \n",
    "                        if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:\n",
    "                            land1 = i*len(grid[0]) + j \n",
    "                            land2 = x*len(grid[0]) + y \n",
    "                            dsu.union(land1,land2)\n",
    "                \n",
    "        island = {}\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    land = i*len(grid[0]) + j \n",
    "                    pa = dsu.find(land)\n",
    "                    if pa in island:\n",
    "                        island[pa].append((i,j))\n",
    "                    else:\n",
    "                        island[pa] = [(i,j)]\n",
    "        # print(island)\n",
    "        island1 = list(island.keys())[0]\n",
    "        island2 = list(island.keys())[1]\n",
    "\n",
    "        q = deque()\n",
    "        step = -1\n",
    "        # 将岛1的点入队\n",
    "        visted1 = set()\n",
    "        for i,j in island[island1]:\n",
    "            visted1.add((i,j))\n",
    "            q.append((i,j))\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                i,j = q.popleft()\n",
    "                for m,n in dirs:\n",
    "                    x = i+m\n",
    "                    y = j+n \n",
    "                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (x,y) not in visted1:\n",
    "                        if grid[x][y] == 1:\n",
    "                            return step\n",
    "                        else:\n",
    "                            visted1.add((x,y))\n",
    "                            q.append((x,y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        if grid is None or len(grid) == 0:\n",
    "            return 0\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        q = deque()\n",
    "        find = False\n",
    "        for i in range(r):\n",
    "            if find:break\n",
    "            for j in range(c):\n",
    "                if grid[i][j]==1:\n",
    "                    self.dfs(grid,q,r,c,i,j)\n",
    "                    find = True\n",
    "                    break\n",
    "        direction = [-1,0,1,0,-1]\n",
    "        level = 0\n",
    "        while q:\n",
    "            s = len(q)\n",
    "            level+=1\n",
    "            while s:\n",
    "                x,y = q.popleft()\n",
    "                for i in range(0,4):\n",
    "                    nx,ny = x+direction[i], y+direction[i+1]\n",
    "                    if nx<0 or nx>=r or ny<0 or ny>=c or grid[nx][ny] == 2:\n",
    "                        continue\n",
    "                    if grid[nx][ny]==1:\n",
    "                        return level\n",
    "                    q.append([nx,ny])\n",
    "                    grid[nx][ny] = 2\n",
    "                s-=1\n",
    "        return 0                \n",
    "            \n",
    "\n",
    "\n",
    "    def dfs(self,grid,q,r,c,i,j):\n",
    "        if i<0 or i>=r or j <0 or j>= c or grid[i][j]==2:\n",
    "            return\n",
    "        if grid[i][j] == 0:\n",
    "            q.append([i,j])\n",
    "            return\n",
    "        grid[i][j] = 2\n",
    "        self.dfs(grid,q,r,c,i+1,j)\n",
    "        self.dfs(grid,q,r,c,i-1,j)\n",
    "        self.dfs(grid,q,r,c,i,j+1)\n",
    "        self.dfs(grid,q,r,c,i,j-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        M, N = len(A), len(A[0])\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        visited = [[0] * N for _ in range(M)]\n",
    "        hasfind = False\n",
    "        que = collections.deque()\n",
    "        for i in range(M):\n",
    "            if hasfind: break\n",
    "            for j in range(N):\n",
    "                if A[i][j] == 1:\n",
    "                    self.dfs(A, i, j, visited, que)\n",
    "                    hasfind = True\n",
    "                    break\n",
    "        step = 0\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            for _ in range(size):\n",
    "                i, j = que.popleft()\n",
    "                for d in dirs:\n",
    "                    x, y = i + d[0], j + d[1]\n",
    "                    if 0 <= x < M and 0 <= y < N:\n",
    "                        visited[x][y] = 1\n",
    "                        if A[x][y] == 1:\n",
    "                            return step\n",
    "                        elif A[x][y] == 0:\n",
    "                            A[x][y] = 2\n",
    "                            que.append((x, y))\n",
    "                        else:\n",
    "                            continue\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "    def dfs(self, A, i, j, visited, que):\n",
    "        if visited[i][j]: return\n",
    "        visited[i][j] = 1\n",
    "        M, N = len(A), len(A[0])\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        if A[i][j] == 1:\n",
    "            que.append((i, j))\n",
    "            A[i][j] = 2\n",
    "            for d in dirs:\n",
    "                x, y = i + d[0], j + d[1]\n",
    "                if 0 <= x < M and 0 <= y < N:\n",
    "                    self.dfs(A, x, y, visited, que)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i,j):\n",
    "            if grid[i][j] == 1:\n",
    "                grid[i][j] = 2\n",
    "                queue.append((i, j))\n",
    "            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:\n",
    "                x = i+dx\n",
    "                y = j+dy\n",
    "                if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] != 0 and grid[x][y] != 2:\n",
    "                    dfs(x, y)\n",
    "        def bfs(i,j):\n",
    "            step = 0\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    a, b = queue.pop(0)\n",
    "                    for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:\n",
    "                        x = a + dx\n",
    "                        y = b + dy \n",
    "                        if 0<=x<len(grid) and 0<=y<len(grid[0]):\n",
    "                            if grid[x][y] == 1:\n",
    "                                return step\n",
    "                            elif grid[x][y] == 0:\n",
    "                                grid[x][y] = 2\n",
    "                                queue.append((x,y))\n",
    "                            else:\n",
    "                                continue\n",
    "                step += 1\n",
    "        queue = list()\n",
    "        for i ,row in enumerate(grid):\n",
    "            for j, ele in enumerate(row):\n",
    "                if ele == 1:\n",
    "                    dfs(i,j)\n",
    "                    return bfs(i,j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# class Solution:\n",
    "#     def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "#         def dfs(x,y):\n",
    "#             if x<0 or x>=n or y<0 or y>=n or grid[x][y]!=1:\n",
    "#                 return \n",
    "#             grid[x][y] = 2\n",
    "#             queue.append((x,y))\n",
    "#             for i,j in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "#                 row = x+i\n",
    "#                 col = y+j\n",
    "#                 # if 0<=row<n and 0<=col<n and grid[row][col]==1:\n",
    "#                 dfs(row,col)\n",
    "#         def bfs(queue):\n",
    "#             steps = 0\n",
    "#             while queue:\n",
    "#                 for _ in range(len(queue)):\n",
    "#                     x,y = queue.popleft()\n",
    "#                     for i,j in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "#                         row = x+i\n",
    "#                         col = y+j \n",
    "#                     if 0<=row<n and 0<=col<n and grid[row][col]==0:\n",
    "#                         queue.append((row,col))\n",
    "#                         grid[row][col]=2\n",
    "#                     if 0<=row<n and 0<=col<n and grid[row][col]==1:\n",
    "#                         return steps\n",
    "#                 steps+=1\n",
    "#             return steps\n",
    "                 \n",
    "#         n = len(grid)\n",
    "#         found = False\n",
    "#         queue = deque()\n",
    "#         for i in range(n):\n",
    "#             if found:\n",
    "#                 break\n",
    "#             for j in range(n):\n",
    "#                 if grid[i][j]==1:\n",
    "#                     # queue.append([(i,j)])\n",
    "#                     dfs(i,j)\n",
    "#                     found = True\n",
    "#                     break  # 跳出当前层的循环体\n",
    "#         return bfs(queue)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or x >= n or y < 0 or y >= n or grid[x][y] != 1:\n",
    "                return\n",
    "            grid[x][y] = 2\n",
    "            queue.append((x, y))\n",
    "            for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                dfs(x + i, y + j)\n",
    "\n",
    "        def bfs(queue):\n",
    "            steps = 0\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    x, y = queue.popleft()\n",
    "                    for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                        row = x + i\n",
    "                        col = y + j\n",
    "                        if 0 <= row < n and 0 <= col < n:\n",
    "                            if grid[row][col] == 0:\n",
    "                                queue.append((row, col))\n",
    "                                grid[row][col] = 2\n",
    "                            elif grid[row][col] == 1:\n",
    "                                return steps\n",
    "                steps += 1\n",
    "            return steps\n",
    "\n",
    "        n = len(grid)\n",
    "        found = False\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            if found:\n",
    "                break\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j)\n",
    "                    found = True\n",
    "                    break  # Break out of the current loop level\n",
    "        return bfs(queue)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x,y):\n",
    "            if x<0 or x>=n or y<0 or y>=n or grid[x][y]!=1:\n",
    "                return \n",
    "            grid[x][y] = 2\n",
    "            queue.append((x,y))\n",
    "            for i,j in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                row = x+i\n",
    "                col = y+j\n",
    "                # if 0<=row<n and 0<=col<n and grid[row][col]==1:\n",
    "                dfs(row,col)\n",
    "        def bfs(queue):\n",
    "            steps = 0\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    x,y = queue.popleft()\n",
    "                    for i,j in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                        row = x+i\n",
    "                        col = y+j \n",
    "                        if 0<=row<n and 0<=col<n and grid[row][col]==0:\n",
    "                            queue.append((row,col))\n",
    "                            grid[row][col]=2\n",
    "                        if 0<=row<n and 0<=col<n and grid[row][col]==1:\n",
    "                            return steps\n",
    "                steps+=1\n",
    "            return steps\n",
    "                 \n",
    "        n = len(grid)\n",
    "        found = False\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            if found:\n",
    "                break\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    # queue.append([(i,j)])\n",
    "                    dfs(i,j)\n",
    "                    found = True\n",
    "                    break  # 跳出当前层的循环体\n",
    "        return bfs(queue)\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "#         def dfs(x, y):\n",
    "#             if x < 0 or x >= n or y < 0 or y >= n or grid[x][y] != 1:\n",
    "#                 return\n",
    "#             grid[x][y] = 2\n",
    "#             queue.append((x, y))\n",
    "#             for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "#                 dfs(x + i, y + j)\n",
    "\n",
    "#         def bfs(queue):\n",
    "#             steps = 0\n",
    "#             while queue:\n",
    "#                 for _ in range(len(queue)):\n",
    "#                     x, y = queue.popleft()\n",
    "#                     for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "#                         row = x + i\n",
    "#                         col = y + j\n",
    "#                         if 0 <= row < n and 0 <= col < n:\n",
    "#                             if grid[row][col] == 0:\n",
    "#                                 queue.append((row, col))\n",
    "#                                 grid[row][col] = 2\n",
    "#                             elif grid[row][col] == 1:\n",
    "#                                 return steps\n",
    "#                 steps += 1\n",
    "#             return steps\n",
    "\n",
    "#         n = len(grid)\n",
    "#         found = False\n",
    "#         queue = deque()\n",
    "#         for i in range(n):\n",
    "#             if found:\n",
    "#                 break\n",
    "#             for j in range(n):\n",
    "#                 if grid[i][j] == 1:\n",
    "#                     dfs(i, j)\n",
    "#                     found = True\n",
    "#                     break  # Break out of the current loop level\n",
    "#         return bfs(queue)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, A: List[List[int]]) -> int:\n",
    "        source = collections.deque()\n",
    "        m = len(A)\n",
    "        n = len(A[0])\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n or A[i][j] == 0: return\n",
    "            A[i][j] = 0\n",
    "            source.append((i, j))\n",
    "            for (r, c) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:\n",
    "                dfs(r, c)\n",
    "        find = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if A[i][j] == 1 and not find:\n",
    "                    dfs(i,j)\n",
    "                    find = True\n",
    "        seen = set(source)\n",
    "        level = 0\n",
    "        while source:\n",
    "            size = len(source)\n",
    "            for s in range(size):\n",
    "                i,j = source.popleft()\n",
    "                for r,c in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:\n",
    "                    if r< 0 or c < 0 or r >= m or c >= n or (r,c) in seen: continue\n",
    "                    if A[r][c] == 0:\n",
    "                        source.append((r,c))\n",
    "                        seen.add((r,c))\n",
    "                    else:\n",
    "                        return level\n",
    "            level += 1\n",
    "        return level\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            q.append((i, j))\n",
    "            grid[i][j] = 2\n",
    "            for a, b in pairwise(dirs):\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:\n",
    "                    dfs(x, y)\n",
    "\n",
    "        n = len(grid)\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque()\n",
    "        i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])\n",
    "        dfs(i, j)\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                for a, b in pairwise(dirs):\n",
    "                    x, y = i + a, j + b\n",
    "                    if 0 <= x < n and 0 <= y < n:\n",
    "                        if grid[x][y] == 1:\n",
    "                            return ans\n",
    "                        if grid[x][y] == 0:\n",
    "                            grid[x][y] = 2\n",
    "                            q.append((x, y))\n",
    "            ans += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "      def dfs(i, j):\n",
    "        q.append((i, j))\n",
    "        grid[i][j] = 2\n",
    "        for a, b in pairwise(dirs):\n",
    "          x, y = i + a, j + b\n",
    "          if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:\n",
    "            dfs(x, y)\n",
    "      n = len(grid)\n",
    "      dirs =(-1, 0, 1, 0, -1)\n",
    "      q = deque()\n",
    "      i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])\n",
    "      dfs(i, j)\n",
    "      ans = 0\n",
    "      while 1:\n",
    "        for _ in range(len(q)):\n",
    "          i, j = q.popleft()\n",
    "          for a, b in pairwise(dirs):\n",
    "            x, y = i+a, j+b\n",
    "            if 0<=x<n and 0<=y<n:\n",
    "              if grid[x][y]==1:\n",
    "                return ans\n",
    "              if grid[x][y]==0:\n",
    "                grid[x][y]=2\n",
    "                q.append((x,y))\n",
    "        ans+=1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            q.append((i, j))\n",
    "            grid[i][j] = 2\n",
    "            for a, b in pairwise(dirs):\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:\n",
    "                    dfs(x, y)\n",
    "\n",
    "        n = len(grid)\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque()\n",
    "        i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])\n",
    "        print(f\"i, j:{i, j}\")\n",
    "        dfs(i, j)\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                for a, b in pairwise(dirs):\n",
    "                    x, y = i + a, j + b\n",
    "                    if 0 <= x < n and 0 <= y < n:\n",
    "                        if grid[x][y] == 1:\n",
    "                            return ans\n",
    "                        if grid[x][y] == 0:\n",
    "                            grid[x][y] = 2\n",
    "                            q.append((x, y))\n",
    "            ans += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestBridge(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        #dfs标记\n",
    "        def dfs(r: int, c: int, nn: int, grid: List[List[int]]):\n",
    "            if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] == nn or grid[r][c]==0:\n",
    "                return\n",
    "            grid[r][c] = nn\n",
    "            for a, b in dir:\n",
    "                dfs(r + a, c + b, nn, grid)\n",
    "        #不同的岛加入不同的队列\n",
    "        flag=True\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j, 2, grid)\n",
    "                    flag=False\n",
    "                    break\n",
    "            if not flag:\n",
    "                break\n",
    "\n",
    "        queue1, queue2 = [], []\n",
    "        dic1,dic2=dict(zip([x*n+y for x in range(n) for y in range(n)],[-1]*n*n)),dict(zip([x*n+y for x in range(n) for y in range(n)],[-1]*n*n))\n",
    "\n",
    "        for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        queue1.append([i, j])\n",
    "                        dic1[n*i+j]=0\n",
    "                    elif grid[i][j] == 2:\n",
    "                        queue2.append([i, j])\n",
    "                        dic2[n*i+j]=0\n",
    "\n",
    "        def update(queue: List, dic1: {}, dic2: {}, step: int):\n",
    "                a, b = queue.pop(0)\n",
    "                for x, y in dir:\n",
    "                    c, d = a + x, b + y\n",
    "                    if c < 0 or c >= n or d < 0 or d >= n or dic1[n * c + d] >= 0:\n",
    "                        continue\n",
    "                    if dic2[n * c + d] >= 0:\n",
    "                        return dic2[n * c + d] + step -1\n",
    "                    else:\n",
    "                        dic1[n * c + d] = step\n",
    "                        queue.append([c,d])\n",
    "                return -1\n",
    "\n",
    "        #对较小的岛bfs\n",
    "        count1,count2 = 0,0\n",
    "        while queue1 and queue2:\n",
    "            if len(queue1) > len(queue2) > 0:\n",
    "                queue1, queue2 = queue2, queue1\n",
    "                dic1, dic2 = dic2, dic1\n",
    "                count1,count2=count2,count1\n",
    "            nn = len(queue1)\n",
    "            count1 += 1\n",
    "            while nn > 0:\n",
    "                ans = update(queue1, dic1, dic2, count1)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "                nn -= 1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
